/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.Map.Entry;
import java.util.TreeMap;

/**
 * @author zhong
 *
 */
public class KClosestPointstoOrigin {
	public int[][] kClosest(int[][] points, int K) {
		TreeMap<Integer, ArrayList<int[]>> distAndPoint = new TreeMap<>();
		for (int i = 0; i < points.length; i++) {
			int[] j = points[i];
			int dist = j[0] * j[0] + j[1] * j[1];
			if (distAndPoint.containsKey(dist)) {
				distAndPoint.get(dist).add(j);
			} else {
				ArrayList<int[]> list = new ArrayList<>();
				list.add(j);
				distAndPoint.put(dist, list);
			}
		}
		int[][] res = new int[K][];
		int i = 0;
		while (i < K) {
			Entry<Integer, ArrayList<int[]>> dist = distAndPoint.pollFirstEntry();
			for (int[] js : dist.getValue()) {
				res[i++] = js;
			}
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] points = { { 1, 3 }, { -2, 2 } };
		int K = 1;
		int[][] res = (new KClosestPointstoOrigin().kClosest(points, K));
		for (int[] is : res) {
			System.out.println(is[0] + "," + is[1]);
		}
	}

}
